
import java.util.Random;

/**
 * class Lis
 * longest increasing subsequence algorithm
 */
public class LisAlgorithm {
    /**
     * print
     */
    public static void printLis(int []a, int []b, int current) {
        if (b[current] >= 0) {
            printLis(a, b, b[current]);
        }
        System.out.printf("%d ", a[current]);
    }

	/**
	 */
    public static void lis(int []a, int len) {
        int i, j;
        int []f = new int[len];  /* f[i]: length of lis which ends with a[i] */
        int []b = new int[len]; /* a[b[i]] -> a[i] */

        f[0] = 1;
        b[0] = -1;
        for (i = 1; i < len; i++) {
            f[i] = 1;
            b[i] = -1;
            for (j = 0; j < i; j++) {
                if (a[j] < a[i] && f[j] > f[i] - 1) {
                    f[i] = f[j] + 1;
                    b[i] = j;
                }
            }
        }
        /* find the last element of lis */
        j = f[0];
        for (i = 0; i < len; i++)
            if (f[i] > j)
                j = i;
        printLis(a, b, j);
        System.out.printf("\n");
    }

	/**
	 */
    public static void main(String []args) {
        int i, j;
        int n[] = {1000, 3000, 200000};
        int []a;
		Random r = new Random();

        for (i = 0; i < 3; i++) {
            a = new int[n[i]];
            for (j = 0; j < n[i]; j++)
                a[j] = r.nextInt(n[i]);
            System.out.printf("The longest increasing subsequence of %d random integers is:\n", n[i]);
            lis(a, n[i]);
        }
    }
}

